import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网TOP101之哈希表
 */
public class Test4 {
    /**
     * 给出一个整型数组 numbers 和一个目标值 target
     * 请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列
     * @param numbers int整型一维数组
     * @param target int整型
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int[] ans = new int[2];
        //1. 创建哈希表，数组值为key,下标为value
        HashMap<Integer, Integer> map = new HashMap<>();
        //2. 将数组中的值存放到哈希表中
        for(int i = 0; i < numbers.length; i++) {
            //3. 判断target和数组值的大小，如果(target > numbers[i])（错误说明）
            //   再判断target - numbers[i]是否存在，先放入哈希表中的数据下标一定比还没放进去的小
            //   注意可能一个值小于target(< 0)，一个值大于target，而如果小的先放进去
            //   那么我们还按照target >= numbers[i]进行条件判断，就会出现重大的失误
            if(map.containsKey(target - numbers[i])) {
                ans[0] = map.get(target - numbers[i]) + 1;
                ans[1] = i + 1;
                return ans;
            }else {
                map.put(numbers[i],i);
            }
        }
        return null;
    }

    /**
     * 数组中出现次数超过一半的数字
     * 利用哈希表的方法计算，更优的是博弈论的投票法
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int [] array) {
        //哈希表的写法，key存储值，value存储数量
        HashMap<Integer, Integer> map = new HashMap<>();
        //max用来保存value最大的key和value
        int[] max = new int[2];
        for(int i = 0; i < array.length; i++) {
            int count = 0;
            if(map.containsKey(array[i])) {
                count = map.get(array[i]) + 1;
                map.put(array[i], count);
            }else {
                map.put(array[i], 1);
                count = 1;
            }
            if(count > max[1]) {
                max[0] = array[i];
                max[1] = count;
            }
        }
        return max[0];
    }

    /**
     * 数组中只出现一次的两个数字
     * 哈希表的解法，更优的是异或的解法
     * @param array
     * @return
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        //哈希表的做法
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < array.length; i++) {
            if(set.contains(array[i])) {
                set.remove(array[i]);
            }else {
                set.add(array[i]);
            }
        }
        int[] ans = new int[2];
        int count = 0;
        for(int i = 0; i < array.length; i++) {
            if(set.contains(array[i])) {
                ans[count++] = array[i];
            }
        }
        if(ans[0] > ans[1]) {
            int tmp = ans[0];
            ans[0] = ans[1];
            ans[1] = tmp;
        }
        return ans;
    }

    /**
     * 缺失的第一个正整数
     * 方法一：使用哈希表暴力解法（不改变原数组的内容）
     * 空间复杂度：O(N)
     * 时间复杂度：O(N)
     * @param nums
     * @return
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        //暴力解法 + 哈希表
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for(int i = 1; i <= nums.length + 1; i++) {
            if(!set.contains(i)) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 缺失的第一个正整数
     * 方法二：在原数组上进行类似哈希的操作（修改了原数组的内容）
     * 思路：
     * 前提条件：数组中的数据都不重复        数组长度n + 1，那么最小整数 <= n + 1
     * 设置一个返回值ans = n + 1
     * 1.遍历数组先将原数组上的所有非正数置为 n + 1
     * 2.再遍历数组 将数组中绝对值的值(Math.abs(nums[i]) < n + 1)为1 ~ n的数作为下标
     *   将该下标减一之后对应的位置的值(-1 * nums[Math.abs(nums[i]) - 1])置为相反数
     *   (置为相反数的操作就是为了避免这个位置的数据丢失，相反数后我们仍能通过绝对值取到)
     * 3.最后遍历数组，当数组的值 > 0时，表示整个数组中没有一个位置储存了当前下标 i
     *   那么i + 1就是缺失的第一个正整数，如果数组的值要么小于0，要么等于n + 1，那么结果就是n + 1
     * 空间复杂度：O(1)
     * 时间复杂度：O(N)
     * @param nums
     * @return
     */
    public int minNumberDisappeared1 (int[] nums) {
        // write code here
        int ans = nums.length + 1;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(Math.abs(nums[i]) <= nums.length) {
                nums[Math.abs(nums[i]) - 1] = -1 * nums[Math.abs(nums[i]) - 1];
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                if(i + 1 < ans) {
                    ans = i + 1;
                    return ans;
                }
            }
        }
        return ans;
    }


    /**
     * 三数之和
     * 方法一：
     * 1.先用一个HashMap记录原数组中的值和个数
     * 2.再用一个HashSet保存满足三数相加等于0的三个数的数组，目的是为了去重
     * 3.下来两层for循环，每层for循环时都要把循环的那个数先删除一个
     *   这样确定三数中的两个数，然后利用Map判断剩余的数中是否存在满足条件的
     *   如果存在，由于题目要求三个数需要非降序保存，因此先保存到数组中，再利用Arrays.sort进行排序
     *   排完序之后保存到Set中去重
     *   由于测试样例的答案按照所有组的数非降序存到返回的顺序表中
     *   因此保存到返回的顺序表list之后，还需要调用sort进行排序
     *   而顺序表排序，我们需要传递一个比较器，最后返回
     *
     * 时间复杂度：O(N ^ 2)(查找元素O(N ^ 2),增加元素(set)O(N ^ 2),元素排序O(NlogN))
     * 空间复杂度：O(N ^ 2)(去重的set)
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(num.length < 3) {
            return list;
        }
        //1. 创建一个哈希表，方便查找
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < num.length; i++) {
            Integer count = map.get(num[i]);
            if(count == null) {
                map.put(num[i],1);
            }else {
                map.put(num[i],count + 1);
            }
        }
        //2. 再创建一个哈希表，用来删去那些相同的数组
        HashSet<ArrayList<Integer>> listSet = new HashSet<>();
        for(int i = 0; i < num.length; i++) {
            int Ivalue = map.get(num[i]);
            if(Ivalue == 1) {
                map.remove(num[i]);
            }else {
                map.put(num[i],Ivalue - 1);
            }
            for(int j = i + 1; j < num.length; j++) {
                int Jvalue = map.get(num[j]);
                if(Jvalue == 1) {
                    map.remove(num[j]);
                }else {
                    map.put(num[j],Jvalue - 1);
                }
                if(map.containsKey(-num[i] - num[j])) {
                    ArrayList<Integer> alist = new ArrayList<>();
                    int[] tmp = new int[3];
                    tmp[0] = num[i];
                    tmp[1] = num[j];
                    tmp[2] = -num[i] - num[j];
                    Arrays.sort(tmp);
                    for(int k = 0; k < 3; k++) {
                        alist.add(tmp[k]);
                    }
                    listSet.add(alist);
                }
                if(Jvalue == 1) {
                    map.put(num[j], 1);
                }else {
                    map.put(num[j],Jvalue);
                }
            }
            if(Ivalue == 1) {
                map.put(num[i], 1);
            }else {
                map.put(num[i],Ivalue);
            }
        }
        list.addAll(listSet);
        list.sort(new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                if(o1.get(0) < o2.get(0)) {
                    return -1;
                }else if(o1.get(0) > o2.get(0)) {
                    return 1;
                }else {
                    if(o1.get(1) < o2.get(1)) {
                        return -1;
                    }else if(o1.get(1) > o2.get(1)) {
                        return 1;
                    }
                }
                return 0;
            }
        });
        return list;
    }

    /**
     * 三数之和
     * 方法一改良：先排序，再寻找
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum2(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(num.length < 3) {
            return list;
        }
        Arrays.sort(num);
        //1. 创建一个哈希表，方便查找
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < num.length; i++) {
            Integer count = map.get(num[i]);
            if(count == null) {
                map.put(num[i],1);
            }else {
                map.put(num[i],count + 1);
            }
        }
        //2. 再创建一个哈希表，用来删去那些相同的数组
        HashSet<ArrayList<Integer>> listSet = new HashSet<>();
        for(int i = 0; i < num.length; i++) {
            int Ivalue = map.get(num[i]);
            if(Ivalue == 1) {
                map.remove(num[i]);
            }else {
                map.put(num[i],Ivalue - 1);
            }
            for(int j = i + 1; j < num.length; j++) {
                int Jvalue = map.get(num[j]);
                if(Jvalue == 1) {
                    map.remove(num[j]);
                }else {
                    map.put(num[j],Jvalue - 1);
                }
                if(map.containsKey(- num[i] - num[j])) {
                    ArrayList<Integer> alist = new ArrayList<>();
                    if((- num[i] - num[j]) <= num[i]) {
                        alist.add(- num[i] - num[j]);
                    }
                    alist.add(num[i]);
                    if((- num[i] - num[j]) > num[i] && (- num[i] - num[j]) <= num[j]) {
                        alist.add(- num[i] - num[j]);
                    }
                    alist.add(num[j]);
                    if((- num[i] - num[j]) > num[j]) {
                        alist.add(- num[i] - num[j]);
                    }
                    listSet.add(alist);
                }
                if(Jvalue == 1) {
                    map.put(num[j], 1);
                }else {
                    map.put(num[j],Jvalue);
                }
            }
            if(Ivalue == 1) {
                map.put(num[i], 1);
            }else {
                map.put(num[i],Ivalue);
            }
        }
        list.addAll(listSet);
        list.sort(new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                if(o1.get(0) < o2.get(0)) {
                    return -1;
                }else if(o1.get(0) > o2.get(0)) {
                    return 1;
                }else {
                    if(o1.get(1) < o2.get(1)) {
                        return -1;
                    }else if(o1.get(1) > o2.get(1)) {
                        return 1;
                    }
                }
                return 0;
            }
        });
        return list;
    }

    /**
     * 三数之和
     * 方法二：双指针
     * 时间复杂度：O(N ^ 2)(查找元素O(N ^ 2),元素排序O(NlogN))
     * 空间复杂度：O(N)返回元素的顺序表list
     * @param num
     * @return
     */
    public ArrayList<ArrayList<Integer>> threeSum3(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        int n = num.length;
        if(n < 3) {
            return list;
        }
        //注意：由于题目要求去重，因此相同元素的三元组我们只算一次，三元组三个元素都需要去重
        //1.排序
        Arrays.sort(num);
        //2.从头开始遍历，确定第一个元素，当不足三个元素的时候，就可以结束循环
        for(int i = 0; i < n - 2; i++) {
            //当元素不是第一个并且和前一个元素相同时，我们就直接跳过
            if(i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            //3.设置第一个元素的相反数target，然后按照target寻找其他两个元素
            int target = -num[i];
            //4.其他两个元素采用双指针的办法，小的初始位置在第一个元素之后的第一个元素，大的在最后一个元素的位置
            int left = i + 1;
            int right = n - 1;
            //同一个target可能有多组不同的元素
            while(left < right) {
                //5.双向遍历，判断是否存在两个元素加起来是target
                if(num[left] + num[right] == target) {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(num[i]);
                    tmp.add(num[left]);
                    tmp.add(num[right]);
                    //保存
                    list.add(tmp);
                    //假设num[left] = 1,num[right] = 2,我们就要保证left指向最后一个1，rihgt指向最前面的那个2
                    //方便我们之后left++,和right--指向新的元素
                    while(left + 1 < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    while(left < right - 1 && num[right] == num[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }else if(num[left] + num[right] < target) {
                    left++;
                }else {
                    right--;
                }
            }
        }
        return list;
    }
}
